package com.simon.study.algorithm.review;


/**
 * <p>
 *
 * @author simon
 * @date 2022/8/31 4:48 下午
 */
public class Kmp {

    public static void main(String[] args) {
        String txt = "abaccacc";
        String aa  = "hahah";
        System.out.println(kmpIndexOf(txt, aa));
        aa  = "ccb";
        System.out.println(kmpIndexOf(txt, aa));

    }

    public static int kmpIndexOf(String source, String target){
        char[] schs = source.toCharArray(), tchs = target.toCharArray();

        int si = 0, ti = 0;
        int[] next = getNext(tchs);

        while (si < schs.length && ti < tchs.length){
            if(schs[si] == tchs[ti]){ si++; ti++; }
            else if(next[ti] == -1){ si++; }
            else{
                ti = next[ti];
            }
        }

        return ti == tchs.length ? si - ti : -1;
    }


    public static int[] getNext(char[] chs){
        int[] next = new int[chs.length];

        next[0] = -1;
        int i = 2, cn = 0;

        while (i < chs.length){
            if(chs[i-1] == chs[cn]){
                next[i++] = ++cn;
            }else if(cn > 0){
                cn = next[cn];
            }else{
                next[i++] = 0;
            }
        }

        return next;
    }
}
